package dataStructLinkedList;

public class MyLinkedList {

    class Node {
        public int val;  // 存储的数据
        public Node next;  // 存储下一个节点的地址
        public Node(int val){
            this.val = val;
        }
    }

    public Node head; //  当前链表的头结点

    public void createLink(){
        Node node1 = new Node(12);
        Node node2 = new Node(45);
        Node node3 = new Node(23);
        Node node4 = new Node(90);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        head = node1;
    }
    // 遍历链表
    public void display() {
        Node tmp = head;
        while (tmp != null){
            System.out.print(tmp.val+" ");
            tmp = tmp.next;
        }
    }
    //查找是否包含关键字key是否在单链表当中
    public boolean contains(int key){
        Node tmp = head;
        while (tmp != null){
            if(tmp.val == key){
                return true;
            }
            tmp = tmp.next;
        }
        return false;
    }
    //得到单链表的长度
    public int size(){
        int count = 0;
        Node tmp = head;
        while (tmp != null){
            count++;
            tmp = tmp.next;
        }
        return count;
    }
    //头插法
    public void addFirst(int data){
        Node node0 = new Node(data);
        node0.next = head;
        head = node0;
    }
    //尾插法
    public void addLast(int data){
        Node nodeLast = new Node(data);
        if(head == null){
            head = nodeLast;
            return;
        }
        Node tmp = head;
        while (tmp.next != null){
            tmp = tmp.next;
        }
        tmp.next = nodeLast;
    }
    //任意位置插入,第一个数据节点为0号下标
    public void addIndex(int index,int data) throws ListIndexOutOfException{
        //  也可能下标不合法，比如负数
        checkIndex(index);
        Node addIndex = new Node(data);
        //  如果插入的下标为0 ，相当于头插法
        if(index == 0){
            addFirst(data);
            return;
        }
        //  如果插入的下标为最后 ，相当于尾插法
        if(index == size()){
            addLast(data);
            return;
        }
        //  下标在范围内的情况
        Node tmp = findIndexDelOne(index);
        addIndex.next = tmp.next;
        tmp.next = addIndex;

    }
    //   找到index-1 位置的节点的地址
    private Node findIndexDelOne(int index){
        Node tmp = head;
        int count = 0;
        while (count != index-1){
            count++;
            tmp = tmp.next;
        }
        return tmp;
    }
    //   判断index位置是否合法，超出范围就抛出异常
    private void checkIndex(int index) throws ListIndexOutOfException{
        if(index < 0 || index > size()){
            throw new RuntimeException("index位置不合法");
        }
    }




    //删除第一次出现关键字为key的节点
    public void remove(int key){
        //  如果key在头结点head
        if(head.val == key){
            head = head.next;
            return;
        }
        //  如果key在head之后的节点上
        Node cur = findPreKey(key);
        if(cur == null){
            return;
        }
        Node del = cur.next; // 要删除的节点
        cur.next = del.next;
    }
    //  找到key的前一个节点
    private Node findPreKey(int key){
        if(head == null){
            return  null;
        }
        Node tmp = head;
        while (tmp.next != null){            //  这个地方要着重 理解 ！！！！！！！！！！！！！！
            if(tmp.next.val == key){         //  这个地方要着重 理解 ！！！！！！！！！！！！
                return tmp;
            }
            tmp = tmp.next;
        }
        return null;  // 没有要删除的节点
    }


    //删除所有值为key的节点
    public void removeAllKey(int key){

        //  如果链表为空，退出
        if(head == null){
            return;
        }
        // 定义两个指针
        Node pre = head;
        Node cur = head.next;
        while (cur != null){
            if(cur.val == key){
                pre.next = cur.next;
                cur = cur.next;
            }else {
                pre = cur;
                cur = cur.next;
            }

        }
        if(head.val == key){
            head = head.next;
        }
    }


    //  清空 链表
    public void clear() {
        head = null;
    }

//====================================================================
//====================================================================
//====================================================================
//====================================================================
    // 头插法
public void addFirst2(int data){
    Node add = new Node(data);
    add.next = head;
    head = add;
}
    //尾插法
    public void addLast2(int data){
        Node add = new Node(data);
        if (head == null){
            head = add;
            return;
        }
        Node cur = head;
        while ( cur.next != null ){
            cur = cur.next;
        }
        cur.next = add;
    }

//    //任意位置插入,第一个数据节点为0号下标
    public boolean addIndex2(int index,int data){
        if (head == null){
            return false;
        }
        if (index < 0 ){
            return false;
        }
        int curSize = 0; // 当前下标
        Node add = new Node(data);
        Node cur = head;
        while (curSize != index-1 && cur.next != null){
            cur = cur.next;
            curSize++;
        }
        add.next = cur.next;
        cur.next = add;
        return true;
    }

//    //查找是否包含关键字key是否在单链表当中
//    public boolean contains2(int key);
//    //删除第一次出现关键字为key的节点
//    public void remove2(int key);
//    //删除所有值为key的节点
//    public void removeAllKey2(int key);
//    //得到单链表的长度
//    public int size2();
//    public void display2();
//    public void clear2();

}
